Range Minimum QueryによるLCA
Abstract
Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各辺の始点 init, 終点 end, 重み weight
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
LCA計算の前処理
Input
なし
Output
根からのEulerツアーで通る順に頂点の深さと頂点の組が入ったリスト eulerian_tour
根からの深さ depth
根からの各頂点への距離 dist
根からのEulerツアーで, 各頂点が初めて現れるインデックスを記録したリスト first_visit
RMQ用のセグメント木 sg
Time complexity
$ O(|V|)time.
LCAの計算
Input
グラフの2頂点 u, v
Output
u と v のLCA lca
Time complexity
$ O(\log |V|)time.
2頂点の距離計算
Input
グラフの2頂点 u, v
Output
u と v の距離 d
Time complexity
$ O(\log |V|)time.
code:python
class LCA:
def __init__(self, N):
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, weight, undirected=True):
self.Einit.append((end, weight)) if undirected: self.Eend.append((init, weight)) def lca_initialize(self):
self._eulerian_tour()
self.sg = SegmentTree(self.euler_tour, min, (float('inf'),))
def _eulerian_tour(self):
N, E = self.N, self.E
self.euler_tour = euler_tour = [] # Eulerian tour from the root (0)
self.depth = depth = -1 * N # depthv: the depth of the vertex v from the root self.dist = dist = float('inf') * N # distv: the distance of the vertex v from the root. self.first_visit = first_visit = -1 * N d = 0 # current depth
while stack:
v, p, l, st = stack.pop()
euler_tour.append((d, v))
if st == 0: # visited v for the first time
depthv = d; first_visitv = len(euler_tour) - 1; distv = l n_children = 0
if u == p: continue
if n_children == 0:
n_children += 1
else:
n_children += 1
if n_children == 0: # v is a leaf
d -= 1
else:
d += 1
elif st == 1: # now searching
d += 1
else: # search finished
d -= 1
def lca(self, u, v):
ui, vi = self.first_visitu, self.first_visitv if ui > vi: ui, vi = vi, ui
return self.sg.fold(ui, vi)1 def distance(self, u, v):
dist = self.dist
w = self.lca(u, v)
return distu + distv - 2 * distw Verification
References